#include<stdio.h>

void Swap(int*a,int*b)
{
    int c=0;
    c = *a;
    *a = *b;
    *b = c;
}

void PrintArray(int*a,int size)
{
    for(int i=0;i<size;i++)
    printf("%d ",a[i]);
    printf("\n");
}
//冒泡排序
void BubbleSort(int *a,int size)
{
    for( int i=0; i < size ; i++)//外循环代表 次数
    {
        int flag=0;
        for(int j=0; j < size - i - 1;j++)
        {
            if(a[j] > a[j+1])
            {   flag = 0;
                Swap(&a[j],&a[j+1]);
            }
        }
        if(flag == 0)
            break;
     }
}



//插入排序
void InsertSort(int *a, int size)
{
    for(int i = 1 ; i < size; i++)  //要插入的数的下标
    {
        int j = i; //当前要插入的数的下标
        int temp = a[i]; //当前插入的数的值
        for( ;j >0 ; j--)
        {
            if(a[j-1] > temp) //前面的数比我大
            {
                a[j] = a[j-1];
            }
            else  //前面的数比我小
            break;
        }
        a[j] = temp; 
    }   
}



//选择排序: 找到后面的序列中最小的值，交换到最左边
void ChooseSort(int *a,int size)
{
    for(int i=0; i<size-1; i++)
    {
        int min = i;        //假设当前就是最小位置

        for(int j = i+1 ; j < size ;j++ ) //遍历后面的所有值
        {
            if(a[min] > a[j] )                  
            {
                min = j;                  //找到一个值比当前值小，更换下标
            }
        }
        Swap(&a[i],&a[min]);
    }
}



//双指针版本的选择排序
void ChooseSort2(int*a,int size)
{
    int left = 0;//左指针
    int right = size-1;//右指针
    while(left < right)
    {
        int min = left, max = right;
        for(int i=left;i <= right ; i++)
        {
            if(a[min]>a[i])
                min = i;
            if(a[i]>a[max])
                max = i;
        }
        Swap(&a[left],&a[min]);
        //如果极值在两端，可能会换两次
        if(max == left)
        {
            max = min;
        }
        Swap(&a[right],&a[max]);
        left++;
        right--;
    }
}




//快速排序：双指针 加 递归
void FastSort(int *a,int start,int end)
{
    if(start >= end)
        return;
    
    int left = start;
    int right = end;
    
    int temp = a[left];//将最左边的值定为基准值
   
    while(left < right)
    {
        //右边往左动，找比基准值小的数
        while(a[right] > temp && left < right)
            right--;
        
        if(left < right)
        {
            a[left++] = a[right];//把右边的比基准值小的数扔到左边的指针
        }
        
        //左边往右边动，找比基准值大的数
        while(a[left] < temp && left < right)
            left++;
        if(left < right)
        {
            a[right--] = a[left];//把左边比基准值大的数扔到右边
        }
    }
    a[left] = temp;

    //递归
    FastSort(a,start,left - 1);
    FastSort(a,right+1,end);
}





// 二分法
int BinarySearch(int*a,int size,int element)
{
    int left = 0;
    int right = size -1;
    while(left <= right)
    {
        // int mid = left + (right - left) / 2;
         int mid = (left & right) +((left ^ right) >> 1);
        if(a[mid]>element)
        {
            right = mid -1;
        }
        else if(a[mid]<element)
        {
            left = mid +1;
        }
        else
            return mid;
    }
    return -1;
}








int main()
{
    int a[5] = {23,56,24,15,67};
    // BubbleSort(a,5);
    FastSort(a,0,4);
    PrintArray(a,5);

    printf("%d\n",BinarySearch(a,5,56));


    return 0;
}